package 题目集.线段树or树状数组.线段树;

import org.junit.Test;

import java.io.*;
import java.util.Arrays;
import java.util.Random;

/**
 * https://www.luogu.com.cn/problem/P4145
 * 别听题哔哔赖赖
 * 题意：给你一个整数序列，
 * 有两个操作
 * 0：对l,r区间开方
 * 1：对l,r区间求和
 *
 * 知识补给：势能分析。
 *  对某个数进行无论多少次操作，操作前和操作后结果不变，则称该数没有势能，反之则叫有势能。
 *
 * 本题思路：
 *  而对于开方操作，一旦数字降到1，则没有必要继续对该数进行操作。
 *  所以我们可以维护一个区间最大值，如果该区间最大值为1，则不进行区间操作。
 *  这个结构我们可以使用线段树维护，虽然无法使用线段树的懒标记（对于开方操作，无法通过o1时间，从子范围推出结果），导致修改操作可能会遍历整棵树。
 *  但即使这样，每个数也不会操作太多次（10^12开方 6次后就为1了）。我们更需要的是判断区间是否需要继续操作，和快速求区间结果
 */
public class ch06_势能分析模板 {

    static int n, m;
    static Node[] tree;
    static long[] src;
    static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public static void main(String[] args) {
        Reader sc = new Reader();
        n = sc.nextInt();
        int tn = (int) Math.pow(2, 1 + Math.ceil(Math.log(n) / Math.log(2)));
        src = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            src[i] = sc.nextLong();
        }
        tree = new Node[tn];
        build(1, 1, n);
        m = sc.nextInt();
        int op, l, r;
        for (int i = 0; i < m; i++) {
            op = sc.nextInt();
            l = sc.nextInt();
            r = sc.nextInt();
            if (l>r){   //这题的l,r可能是反的。。。
                l=l^r;
                r=l^r;
                l=l^r;
            }
            if (op == 0) {
                sqrt(1, l, r);
            } else {
                long sum = sum(1, l, r);
                pw.println(sum);
            }
        }
        pw.flush();
    }

    public static void build(int i, int l, int r) {
        tree[i] = new Node(l, r);
        if (l == r) {
            tree[i].sum = src[l];
            tree[i].max = src[l];
        } else {
            int m = l + r >> 1;
            build(i << 1, l, m);
            build(i << 1 | 1, m + 1, r);
            pull(i);
        }
    }

    public static void sqrt(int i, int l, int r) {
        if (tree[i].max <= 1) return;
        if (tree[i].l == tree[i].r) {
            tree[i].sum = (long) Math.sqrt(tree[i].sum);
            tree[i].max = tree[i].sum;
            return;
        }
        int m = tree[i].l + tree[i].r >> 1;
        if (l <= m) sqrt(i << 1, l, r);
        if (m < r) sqrt(i << 1 | 1, l, r);
        pull(i);
    }

    private static long sum(int i, int l, int r) {
        if (l <= tree[i].l && tree[i].r <= r) return tree[i].sum;
        int m = tree[i].l + tree[i].r >> 1;
        long res = 0;
        if (l <= m) res += sum(i << 1, l, r);
        if (m < r) res += sum(i << 1 | 1, l, r);
        return res;
    }

    public static void pull(int i) {
        int l = i << 1;
        int r = l | 1;
        tree[i].sum = tree[l].sum + tree[r].sum;
        tree[i].max = Math.max(tree[l].max, tree[r].max);
    }

    static class Node {
        int l, r;
        //一个用于存区间结果，一个用于判断是否需要继续操作
        long sum, max;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }

    static class Reader {
        static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public Reader(Object... o) {
        }

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {}
            return (int) in.nval;
        }

        public long nextLong() {
            try {
                in.nextToken();
            } catch (Exception ignored) {}
            return (long) in.nval;
        }
    }


    @Test
    public void test() {
        int maxN = 1000, maxM = 100;
        long maxV= (long) 1e10;
        int count = 10000;
        while (count-- > 0) {
            compare(maxN, maxM,maxV);
        }
    }

    static Random random = new Random();

    public static void compare(int maxN, int maxM,long maxV) {
        long[] origin = new long[maxN + 1];
        for (int i = 1; i < origin.length; i++) {
            origin[i] = Math.abs(random.nextLong());
        }
        check = origin.clone();
        src = origin.clone();
        int n = origin.length - 1;
        int tn = (int) Math.pow(2, 1 + Math.ceil(Math.log(n) / Math.log(2)));
        tree = new Node[tn];
        build(1, 1, n);
        int[][] ops = new int[maxM][3];
        for (int i = 0; i < maxM; i++) {
            ops[i][0] = random.nextInt(2);
            ops[i][1] = random.nextInt(maxN) + 1;
            ops[i][2] = random.nextInt(maxN) + 1;

            int l = Math.min(ops[i][1], ops[i][2]);
            int r = Math.max(ops[i][1], ops[i][2]);

            ops[i][1] = l;
            ops[i][2] = r;
            if (ops[i][0] == 0) {
                sqrt(1, l, r);
                checkSqrt(l, r);
            } else {
                long ans1 = checkSum(l, r);
                long ans2 = sum(1, l, r);
                if (ans1 != ans2) {
                    System.out.println(i + "：出错了!\t ans=" + ans1 + "\terror=" + ans2);
                    for (int[] op : ops) {
                        System.out.println(Arrays.toString(op));
                    }
                    break;
                }
            }
        }
    }

    static long[] check;

    public static void checkSqrt(int l, int r) {
        for (int i = l; i <= r; i++) check[i] = (long) Math.sqrt(check[i]);
    }

    public static long checkSum(int l, int r) {
        long res = 0;
        for (int i = l; i <= r; i++) res += check[i];
        return res;
    }

}
